package LeetCode;

public class WordSearch
{
  
//shorter
  public boolean exist1(char[][] board, String word) {
    int numRows=board.length;
    int numCols=board[0].length;        
    boolean [][]visited=new boolean[numRows][numCols];
    for(int i=0;i<numRows;i++)
    {
        for(int j=0;j<numCols;j++)
        {
            //DFS starting from each cell
            if(exist(board, i, j, 0, visited, word))
                return true;
            //reset visited    
            visited[i][j] = false;
        }
    }
    return false;
 }

 //DFS for substring starting at position i of word
 public boolean exist(char[][] board, int row, int col, int i, boolean[][]visited, String word)
 {
    if(i==word.length())
    {
        return true;
    }
    if(row<0||row>=board.length||col<0 || col>=board[0].length)
    {
        return false;
    }
    if(!visited[row][col])
    {
        //set the current position of board as visited
        if(board[row][col]==word.charAt(i))
        {
            visited[row][col]=true; 
            //DFS on its four neighbor
            boolean case1=exist(board, row+1, col, i+1, visited, word);
            boolean case2=exist(board, row-1, col, i+1, visited, word);
            boolean case3=exist(board, row, col+1, i+1, visited, word);
            boolean case4=exist(board, row, col-1, i+1, visited, word);                
            return case1||case2||case3||case4;                 
        }            
    }
    return false;
 }
  
  
  //ETL
  
  //recursive, one more matrix to store the info whether this 
  //char has been used or not
  public boolean exist(char[][] board, String word)
  {
    // Start typing your Java solution below
    // DO NOT write main() function
    int m = board.length;
    if (m == 0) return word.length() == 0;
    ;
    int n = board[0].length;
    if (n == 0) return false;
    boolean[][] visited = new boolean[m][n];

    for (int i = 0 ; i < m ; i++) {
      for (int j = 0 ; j < n ; j++) {
        if (exist(board, word, 0, visited, i, j)) {
          return true;
        }
        visited[i][j] = false;
      }
    }
    return false;
  }

  public boolean exist(char[][] board, String word, int level,
      boolean[][] visited, int r, int c)
  {
    int m = board.length;
    int n = board[0].length;
    if (board[r][c] != word.charAt(level)) return false;
    if (level == word.length() - 1) return true;

    boolean up = false, down = false, left = false, right = false;
    visited[r][c] = true;
    // up
    if (r - 1 >= 0 && !visited[r - 1][c]) {
      up = exist(board, word, level + 1, visited, r - 1, c);
      visited[r - 1][c] = false;
    }
    if (up) return true;
    // down
    if (r + 1 < m && !visited[r + 1][c]) {
      down = exist(board, word, level + 1, visited, r + 1, c);
      visited[r + 1][c] = false;
    }
    if (down) return true;

    // left
    if (c - 1 >= 0 && !visited[r][c - 1]) {
      left = exist(board, word, level + 1, visited, r, c - 1);
      visited[r][c - 1] = false;
    }
    if (left) return true;

    // right
    if (c + 1 < n && !visited[r][c + 1]) {
      right = exist(board, word, level + 1, visited, r, c + 1);
      visited[r][c + 1] = false;
    }
    if (right) return true;

    return false;
  }

  
  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    WordSearch w = new WordSearch();
    System.out.println(w.exist1(new char[][]{{'a','a'}}, "aa"));
    
  }

}
